<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>计算点集的包络多边形</title>
    <style>
      * {
        margin: 0;
        padding: 0;
        box-sizing: border-box;
        list-style: none;
      }

      .box {
        width: 1000px;
        height: 800px;
        margin: 30px auto;
        display: flex;
        border: 1px solid;
      }

      #myCanvas {
        margin: auto;
        border: 1px solid;
      }
    </style>
  </head>

  <body>
    <div class="box">
      <canvas id="myCanvas" height="750" width="950" tabindex="333"></canvas>
    </div>
  </body>
  <script>
    console.time("!!!!");
    const pointx = document.getElementById("pointx");
    const pointy = document.getElementById("pointy");
    let ids = null;
    /* * @type { HTMLCanvasElement } */
    const myCanvas = document.getElementById("myCanvas");
    const ctx = myCanvas.getContext("2d");
    /* 测试开始 */
    // 多边形
    // 点集合，至少 3 个点
    // const testpointArr = [
    //   { x: 100, y: 100 }, //
    //   { x: 200, y: 100 }, //
    //   { x: 150, y: 150 }, //
    //   { x: 200, y: 200 }, //
    //   { x: 200, y: 100 }, //
    //   { x: 200, y: 100 }, //
    //   { x: 540, y: 200 }, //
    //   { x: 140, y: 400 }, //
    //   { x: 20, y: 430 }, //
    //   { x: 200, y: 100 }, //
    //   { x: 258, y: 100 }, //
    //   { x: 200, y: 10 }, //
    //   { x: 400, y: 400 }, //
    //   { x: 540, y: 200 }, //
    //   { x: 900, y: 300 }, //
    //   { x: 200, y: 300 }, //
    //   { x: 480, y: 170 }, //
    //   { x: 100, y: 100 }, //
    //   { x: 200, y: 30 }, //
    //   { x: 200, y: 100 }, //
    //   { x: 200, y: 0 }, //
    //   { x: 500, y: 300 }, //
    //   { x: 500, y: 20 }, //
    //   { x: 480, y: 170 }, //
    // ];
    const testpointArr = [];
    for (let i = 0; i < 20; i++) {
      testpointArr.push({
        x: 0,
        y: 0,
      });
      testpointArr[i].x = Math.random() * 900;
      testpointArr[i].y = Math.random() * 500;
    }
    // 画多个点
    testpointArr.forEach((item) => {
      drawPoint(ctx, item);
    });
    console.log("testpointArr.length :>> ", testpointArr.length);
    // 画点
    var yy = getOutsideMaxPolygonPoint(testpointArr);
    drawPolygon(yy, ctx);
    console.timeEnd("!!!!");

    /* 测试结束，以下都是所用到的函数 */

    // 画多边形，并且求取凸、凹多边形面积
    function drawPolygon(pointArr, ctx, needDraw = true) {
      if (!pointArr || pointArr.length < 2) {
        return null;
      }
      if (needDraw) {
        if (pointArr.length === 2) {
          ctx.save();
          ctx.beginPath();
          ctx.moveTo(pointArr[0].x, pointArr[0].y);
          ctx.lineTo(pointArr[1].x, pointArr[1].y);
          ctx.stroke();
          ctx.closePath();
          ctx.restore();
          return null;
        }
        for (let i = 0; i < pointArr.length; i++) {
          ctx.save();
          ctx.beginPath();
          let num = i + 1;
          if (num >= pointArr.length) {
            num = 0;
          }
          ctx.moveTo(pointArr[i].x, pointArr[i].y);
          ctx.lineTo(pointArr[num].x, pointArr[num].y);
          ctx.stroke();
          ctx.closePath();
          ctx.restore();
        }
      }
      /* 求取面积 */
      if (pointArr.length == 2) {
        return {
          realArea: 0, // 真实面积
          absArea: 0,
        };
      }
      let squareArea = 0;
      let absArea = 0;
      let basePoint = pointArr[0];
      // 转化为相对于起点的各处向量
      let newPointArr = changePointToBase(pointArr[0], pointArr);
      for (let i = 1; i < newPointArr.length; i++) {
        let y = i + 1;
        if (y >= newPointArr.length - 1) {
          y = newPointArr.length - 1;
        }
        squareArea += getOriginTriSquare(newPointArr[i], newPointArr[y]);
        absArea += Math.abs(getOriginTriSquare(newPointArr[i], newPointArr[y]));
      }
      return {
        realArea: Math.abs(squareArea), // 真实面积
        absArea: absArea, // 绝对值面积
      };
    }

    // 画点
    function drawPoint(ctx, point) {
      ctx.save();
      ctx.beginPath();
      ctx.beginPath();
      ctx.arc(point.x, point.y, 3, 0, 2 * Math.PI);
      ctx.closePath();
      ctx.stroke();
      ctx.closePath();
      ctx.restore();
    }

    // 二维向量叉乘的模/三角形面积（以原点为起点）
    // 判断点 point2 是否在 point1 向量的上方/右方/重合
    function cross2Product(point1, point2) {
      // needTriSquare 为 true 是求三角形面积
      // needTriSquare 为 false 是求叉乘的模
      return point1.x * point2.y - point1.y * point2.x;
    }
    /**
     * @description: 求取基于原点的三角形面积
     */
    function getOriginTriSquare(point1, point2) {
      return 0.5 * cross2Product(point1, point2);
    }

    // 求向量点乘，内夹角
    function mutipleProduct(point1, point2) {
      if (!point1 || !point2) {
        return {
          multiNum: 0,
          angel: 0,
        };
      }
      let point1Model = Math.sqrt(point1.x * point1.x + point1.y * point1.y);
      let point2Model = Math.sqrt(point2.x * point2.x + point2.y * point2.y);
      return {
        multiNum: point1.x * point2.x + point1.y * point2.y, // 点积的值
        angel:
          (Math.acos(
            (point1.x * point2.x + point1.y * point2.y) /
              (point1Model * point2Model)
          ) *
            180) /
          Math.PI, // 两向量所成夹角（角度）
      };
    }

    // 计算根据基准点(basePoint)为原点的基础坐标系
    // isHaveSelf: basePoint 是否包含于 otherPoint 中，并且需要剔除出去这个点。
    function changePointToBase(basePoint, otherPoint, isHaveSelf = false) {
      if (isHaveSelf) {
        otherPoint = otherPoint.filter(
          (point) => point.x != basePoint.x && point.y != basePoint.y
        );
      }
      if (!basePoint) {
        throw new Error("多点共线，且没有其他点！");
      }
      return otherPoint.map((point, i) => {
        return {
          ...point, // 保留其他信息
          x: point.x - basePoint.x,
          y: point.y - basePoint.y,
        };
      });
    }

    // 主函数--获取最外层的点
    // 最少 3 个点
    function getOutsideMaxPolygonPoint(pointArr) {
      if (!pointArr) {
        throw new Error("请输入合法数集参数！");
      }
      if (pointArr.length < 3) {
        throw new Error("请输入至少 3 个点！");
      }
      if (pointArr.length > 65) {
        throw new Error("计算时间过长，请输入少于 65 个点！");
      }
      // 处理共线、重复点
      let currPointArr = deleteRepeatPoint(pointArr);
      pointCollinearGroup(currPointArr).forEach((it) => {
        let y = [];
        it.split(",").forEach((item) => {
          y.push(currPointArr[item - 0]);
        });
        saveLineSidePoint(y); // 打标签
      });
      let lastPointArr = currPointArr.filter((item) => !item.__SIDE___);

      // 初始化
      let number = 0; // 计数器，每获取一条边就加 1，最大不会超过 pointArr.length
      let midArr = getOutsidePointOrder(lastPointArr);
      lastPointArr.forEach((it, i) => (it.__INDEX__ = midArr[i]?.__INDEX__));
      let indexPointArr = lastPointArr.filter(
        (point) => point.__INDEX__ !== void 0
      );

      return orderArray(indexPointArr, "__INDEX__");

      function getOutsidePointOrder(pointArr) {
        // 找到这一堆点中最边缘的点(以最左边的点为准)
        let point0;
        if (number === 0) {
          point0 = getMinValue(pointArr, "x");
        } else {
          point0 = pointArr.filter((it) => it.__INDEX__ === number)[0];
        }
        let newPointArr = changePointToBase(point0, pointArr);
        // __INDEX__ 是画边界点的依据
        pointArr.forEach((it, i) => {
          it.__INDEX__ = newPointArr[i]?.__INDEX__;
        });
        // console.log("pointArr>>", pointArr, number);
        let jumpIndex = void 0;
        for (let i = 0; i < newPointArr.length; i++) {
          let newPoint = newPointArr[i];
          if (newPoint.x === 0 && newPoint.y === 0) {
            jumpIndex = i;
            if (newPoint.__INDEX__ !== 0) {
              newPoint.__INDEX__ = number;
            }
            continue;
          }
        }

        let u = [];
        // 找到第一条边和倒数第一条边。
        for (let i = 0; i < newPointArr.length; i++) {
          u[i] = [];
          for (let j = 0; j < newPointArr.length; j++) {
            if (i === jumpIndex || j === jumpIndex) {
              continue;
            }
            if (i === j) {
              continue;
            }
            // 逻辑
            u[i].push(cross2Product(newPointArr[i], newPointArr[j]));
          }
        }

        for (let idx = 0; idx < u.length; idx++) {
          if (u[idx].length && isSameSign(u[idx])) {
            if (u[idx][0] >= 0) {
              if (newPointArr[idx].__INDEX__ === void 0) {
                // 代表逆时针描边，多边形的正数的第一条边
                newPointArr[idx].__INDEX__ = number + 1;
              } else if (newPointArr[idx].__INDEX__ === -1) {
                // 代表此时已经首尾相连，此时跳出循环
                newPointArr[idx].__INDEX__ = number + 1;
                return newPointArr;
              } else {
                console.log("共线或重合！", newPointArr);
              }
            } else {
              if (newPointArr[idx].__INDEX__ === void 0) {
                // 代表逆时针描边，多边形的倒数的第一条边
                newPointArr[idx].__INDEX__ = -1;
              }
            }
          }
        }
        number++;

        return getOutsidePointOrder(newPointArr);
      }
    }

    /* 求两点之间的距离 */
    function getDistanceBeforeTwoPoints(point1, point2) {
      return Math.sqrt(
        Math.pow(point2.y - point1.y, 2) + Math.pow(point2.x - point1.x, 2)
      );
    }
    // 获取数组对象中，某一项的最(小)值
    function getMinValue(objArr, key) {
      if (objArr.length === 0) return null; // 如果数组为空，返回 null

      let minObj = objArr[0]; // 假设第一个点是最小的

      for (let i = 1; i < objArr.length; i++) {
        if (objArr[i][key] < minObj[key]) {
          minObj = objArr[i]; // 更新最小点
        }
      }
      return minObj;
    }
    // 将数组根据某一项进行排序（升序）
    function orderArray(arr, key = "value") {
      return (arr || []).sort((a, b) => a[key] - b[key]);
    }

    // 根据 key 值对数组进行分组
    function arrToGroup(arr, objKey) {
      // 使用 reduce 来分组
      return arr.reduce((acc, item) => {
        const key = item[objKey];
        // 如果不存在就先分配一个数组进行存储
        if (!acc[key]) {
          acc[key] = [];
        }
        // 向存储空间中推入
        acc[key].push(item);
        return acc;
      }, {});
    }

    // 判断一堆数同号或者有 0
    function isSameSign(arr) {
      if (arr.length === 0 || arr.length === 1) {
        // 数组 0 项或者只有 1 项
        return true;
      }
      if (Math.max(...arr) === 0 && Math.min(...arr) === 0) {
        // 全 0
        return true;
      }
      let flag = true;
      if (Math.max(...arr) * Math.min(...arr) < 0) {
        flag = false;
      } else if (Math.max(...arr) * Math.min(...arr) > 0) {
        flag = true;
      } else {
        // 数组中带 0 ，这种情况比较复杂。
        if (Math.min(...arr) === 0 || Math.max(...arr) === 0) {
          // 数组虽然出现 0，但是除了 0 之外都同号
          flag = true;
        } else {
          // 数组虽然出现 0，但是仍然是不同号
          flag = false;
        }
      }

      return flag;
    }

    // 对共线、重复的点进行处理
    // 1 筛选重复点，保留非重复点
    function deleteRepeatPoint(pointArr) {
      const seen = new Set();
      return pointArr.filter((point) => {
        const key = `${point.x},${point.y}`;
        if (seen.has(key)) return false;
        seen.add(key);
        return true;
      });
    }

    // 2 获取点集的三点共线组合(序号)
    function pointCollinearGroup(pointArr, needDeletRepeatPoint = true) {
      let newPoint = pointArr;
      // 去除重复点
      if (needDeletRepeatPoint) {
        newPoint = deleteRepeatPoint(pointArr);
      }
      let repeatPoint = [];

      for (let i = 0; i < newPoint.length; i++) {
        for (let j = 0; j < newPoint.length; j++) {
          if (i === j || j < i) {
            continue;
          }
          for (let ii = 0; ii < newPoint.length; ii++) {
            for (let jj = 0; jj < newPoint.length; jj++) {
              if (ii === jj || jj < ii) {
                continue;
              }
              if (i === ii && j === jj) {
                continue;
              }
              if (j > jj || (j === jj && i > ii)) {
                continue;
              }

              if (
                cross2Product(
                  getPointArray(newPoint[i], newPoint[j]),
                  getPointArray(newPoint[ii], newPoint[jj])
                ) === 0
              ) {
                let yarr = [...new Set([i, j, ii, jj])].sort((a, b) => a - b);
                repeatPoint.push(yarr);
                repeatPoint = repeatPoint.filter((it) => it.length === 3);
              }
            }
          }
        }
      }
      repeatPoint = [...new Set(repeatPoint.map((it) => it.join()))];
      return repeatPoint;
    }

    // 去除掉共线点的中间点，保留两侧点给出一组直线上的点，标记其中处于中间的点
    function saveLineSidePoint(arrPoint) {
      if (!arrPoint) {
        throw new Error("请输入合法点集参数！");
      }
      if (arrPoint.length === 1) {
        throw new Error("输入的点集至少要有 2 个！");
      }
      if (arrPoint.length === 2) {
        return arrPoint;
      }
      let newArrPoint = arrPoint;
      if (arrPoint[0].y === arrPoint[1].y) {
        // 点集成竖直排列
        newArrPoint = orderArray(arrPoint, "x");
        newArrPoint.forEach((point, idx) => {
          if (idx != 0 && idx != newArrPoint.length - 1) {
            point.__SIDE___ = "center";
          }
        });
        return newArrPoint;
      }
      if (arrPoint[0].x === arrPoint[1].x) {
        // 点集成水平排列
        newArrPoint = orderArray(arrPoint, "y");
        newArrPoint.forEach((point, idx) => {
          if (idx != 0 && idx != newArrPoint.length - 1) {
            point.__SIDE___ = "center";
          }
        });
        return newArrPoint;
      }
      // 斜着排列也是一样
      newArrPoint = orderArray(arrPoint, "x"); // 任意找一个基准进行排列
      newArrPoint.forEach((point, idx) => {
        if (idx != 0 && idx != newArrPoint.length - 1) {
          point.__SIDE___ = "center";
        }
      });
      return newArrPoint;
    }

    // 获取 point1 指向 point2 的向量
    function getPointArray(point1, point2) {
      return {
        ...point1,
        ...point2,
        x: point2.x - point1.x,
        y: point2.y - point1.y,
      };
    }

    // 墨卡托坐标系与经纬度坐标的互相转换 --- 注意经纬度的本质是角度，不是弧度
    function mercatorToGeoCoordinate(mokaPoint) {
      // 墨卡托坐标系转化为经纬度坐标
      if (!mokaPoint) {
        throw new Error("输入的点或者点集格式不对！");
        return null;
      }
      const earthRadius = 6378137; // 地球半径
      if (!Array.isArray(mokaPoint)) {
        // 单个点
        return {
          ...mokaPoint,
          x: (mokaPoint.x * 180) / (earthRadius * Math.PI), // 计算经度
          y:
            (180 *
              (2 * Math.atan(Math.exp(mokaPoint.y / earthRadius)) -
                Math.PI / 2)) /
            Math.PI,
        };
      } else {
        return mokaPoint.map((item) => {
          return {
            ...item,
            x: (item.x * 180) / (earthRadius * Math.PI),
            y:
              (180 *
                (2 * Math.atan(Math.exp(item.y / earthRadius)) - Math.PI / 2)) /
              Math.PI,
          };
        });
      }
    }

    function geoToMercatorCoordinate(point) {
      // 经纬度坐标转化为墨卡托坐标系
      if (!point) {
        throw new Error("输入的点或者点集格式不对！");
        return null;
      }
      const earthRadius = 6378137; // 地球半径
      if (!Array.isArray(point)) {
        // 单个点
        return {
          ...point,
          x: earthRadius * degree2Radians(point.x),
          y:
            earthRadius *
            Math.log(Math.tan(Math.PI / 4 + degree2Radians(point.y / 2))),
        };
      } else {
        return point.map((item) => {
          return {
            ...item,
            x: (earthRadius * Math.PI * item.x) / 180,
            y:
              (earthRadius *
                Math.PI *
                Math.log(Math.tan(Math.PI / 4 + item.y / 2))) /
              180,
          };
        });
      }
    }

    // 角度互相转化为弧度
    function degree2Radians(deg, direction = true) {
      if (direction) {
        // 角度转化为弧度
        return (deg * Math.PI) / 180;
      } else {
        // 弧度转化为角度
        return (deg * 180) / Math.PI;
      }
    }
    console.log(geoToMercatorCoordinate({ x: 180, y: 85.0511 }));
  </script>
</html>
